package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入'.' 来形成。你 不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/restore-ip-addresses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-04
 * Time:22:06
 */
public class DFS93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        int[] nums = new int[4];//存放IP地址内的四个整数
        DFS(list,nums,0,0,s);
        return list;
    }
    public void DFS(List<String> list,int[] nums,int index,int start,String s){
        if(index == 4){//将所有字符遍历完正好可以放放了4个
            if(start == s.length()){
                StringBuilder stringBuilder = new StringBuilder();//将这些拼接起来
                for(int i = 0;i < nums.length;i ++){
                    stringBuilder.append(nums[i]);
                    if(i != nums.length - 1){
                        stringBuilder.append('.');
                    }
                }
                list.add(stringBuilder.toString());
            }
            return;
        }
        //字符串遍历完但是不符合IP地址基本要求
        if(start == s.length()){
            return;
        }
        if(s.charAt(start) == '0'){//不能有前导0,因此要是碰到0开头的话就自成一个地址位
            nums[index] = 0;//数组位加一
            DFS(list,nums,index + 1,start + 1,s);
        }
        int num = 0;
        for(int i = start;i < s.length();i ++){
            num = num * 10 + (s.charAt(i) - '0');//可组成的整数
            if(num > 0 && num <= 255){//满足要求
                nums[index] = num;
                DFS(list,nums,index + 1,i + 1,s);
            }else{
                break;//不满足就回溯重新开始排列
            }
        }
    }
}
